package com.sheng.leetcode.year2023.month06.day20;

import org.junit.Test;

import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @author liusheng
 * @date 2023/06/20
 * <p>
 * 1595. 连通两组点的最小成本<p>
 * <p>
 * 给你两组点，其中第一组中有 size1 个点，第二组中有 size2 个点，且 size1 >= size2 。<p>
 * 任意两点间的连接成本 cost 由大小为 size1 x size2 矩阵给出，<p>
 * 其中 cost[i][j] 是第一组中的点 i 和第二组中的点 j 的连接成本。<p>
 * 如果两个组中的每个点都与另一组中的一个或多个点连接，则称这两组点是连通的。<p>
 * 换言之，第一组中的每个点必须至少与第二组中的一个点连接，且第二组中的每个点必须至少与第一组中的一个点连接。<p>
 * 返回连通两组点所需的最小成本。<p>
 * <p>
 * 示例 1：<p>
 * 输入：cost = [[15, 96], [36, 2]]<p>
 * 输出：17<p>
 * 解释：连通两组点的最佳方法是：<p>
 * 1--A<p>
 * 2--B<p>
 * 总成本为 17 。<p>
 * <p>
 * 示例 2：<p>
 * 输入：cost = [[1, 3, 5], [4, 1, 1], [1, 5, 3]]<p>
 * 输出：4<p>
 * 解释：连通两组点的最佳方法是：<p>
 * 1--A<p>
 * 2--B<p>
 * 2--C<p>
 * 3--A<p>
 * 最小成本为 4 。<p>
 * 请注意，虽然有多个点连接到第一组中的点 2 和第二组中的点 A ，但由于题目并不限制连接点的数目，所以只需要关心最低总成本。<p>
 * <p>
 * 示例 3：<p>
 * 输入：cost = [[2, 5, 1], [3, 4, 7], [8, 1, 2], [6, 2, 4], [3, 8, 8]]<p>
 * 输出：10<p>
 * <p>
 * 提示：<p>
 * size1 == cost.length<p>
 * size2 == cost[i].length<p>
 * 1 <= size1, size2 <= 12<p>
 * size1 >= size2<p>
 * 0 <= cost[i][j] <= 100<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/minimum-cost-to-connect-two-groups-of-points">1595. 连通两组点的最小成本</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1595 {

    @Test
    public void test01() {
//        int[][] ints = {{15, 96}, {36, 2}};
//        int[][] ints = {{1, 3, 5}, {4, 1, 1}, {1, 5, 3}};
        int[][] ints = {{2, 5, 1}, {3, 4, 7}, {8, 1, 2}, {6, 2, 4}, {3, 8, 8}};
        List<List<Integer>> cost = Arrays.stream(ints).map(i ->
                Arrays.stream(i).boxed().collect(Collectors.toList())).collect(Collectors.toList());
        System.out.println(new Solution().connectTwoGroups(cost));
    }
}

class Solution {
    public int connectTwoGroups(List<List<Integer>> cost) {
        int m = cost.size(), n = cost.get(0).size();
        final int inf = 1 << 30;
        int[] f = new int[1 << n];
        Arrays.fill(f, inf);
        f[0] = 0;
        int[] g = f.clone();
        for (int i = 1; i <= m; ++i) {
            for (int j = 0; j < 1 << n; ++j) {
                g[j] = inf;
                for (int k = 0; k < n; ++k) {
                    if ((j >> k & 1) == 1) {
                        int c = cost.get(i - 1).get(k);
                        g[j] = Math.min(g[j], g[j ^ (1 << k)] + c);
                        g[j] = Math.min(g[j], f[j] + c);
                        g[j] = Math.min(g[j], f[j ^ (1 << k)] + c);
                    }
                }
            }
            System.arraycopy(g, 0, f, 0, 1 << n);
        }
        return f[(1 << n) - 1];
    }
}
